package com.yt.Test;

import java.util.Arrays;

public class paixu {
	public static void main(String[] args) {
		int[] arr = {5, 4, 4, 4, 5, 3, 2,9, 1};
		insertSort(arr);
		System.out.println(Arrays.toString(arr));
	}                            

	public static void insertSort(int[] arr) {
		for(int i = 1; i < arr.length; i++) {
			//记录初始的值
			int v = arr[i];
			//记录进行插入的位置
			int j = i - 1; 
			//当出现arr[j] > v (升序)时说明该位置的前一个位置就是v应该放入的位置
			for(; j >=0 && arr[j] > v; j--)
				arr[j + 1] = arr[j];
			arr[j + 1] = v;
		}
	}
}
